package _binary_search;

import java.util.ArrayList;

/**
 * 300. 最长递增子序列
 */
public class No300 {
    private ArrayList<Integer> list;

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        list = new ArrayList<>();
        for (int num : nums) {
            int index = lowerBound(num);
            if (index == list.size()) list.add(num);
            else list.set(index, num);
        }
        return list.size();
    }

    private int lowerBound(int x) {
        int n = list.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left >> 1);
            if (list.get(mid) < x) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}
